package leetcode_day._2022._202209._0110;

import general_class.TreeNode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 652. 寻找重复的子树
 * 算法：深度优先搜索
 * 通过前序遍历, 可以找到以当前节点为根节点的所有节点的顺序
 * 不能使用中序遍历
 *
 * @author yzh
 * @version 1.0
 * @date 2022/9/5 21:58
 */
public class _05 {

    Map<String, Integer> map;
    List<TreeNode> ans;
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        map = new HashMap<>();
        ans = new ArrayList<>();
        dfs(root);
        return ans;
    }

    String dfs(TreeNode node) {
        if (node == null) return "";
        String key = new StringBuilder().append(node.val).append("/").append(dfs(node.left))
                .append("/").append(dfs(node.right)).toString();
        int val;
        if((val = map.getOrDefault(key, 0)) == 1) ans.add(node);
        map.put(key, val + 1);
        return key;
    }

}
